#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator>

void counting_sort(const std::vector<int>& unsorted, std::vector<int>& sorted) {
	std::pair<std::vector<int>::const_iterator, std::vector<int>::const_iterator> min_max = std::minmax_element(unsorted.begin(),unsorted.end());
	int min = *min_max.first;
	int max = *min_max.second;
	std::vector<int> c(max-min+1, 0);
	for (int i = 0; i < unsorted.size(); ++i)
		++c[unsorted[i] - min];
	std::partial_sum(c.begin(),c.end(),c.begin());
	sorted.resize(unsorted.size());
	for (int i = unsorted.size()-1; i >=0; --i) {
		sorted[c[unsorted[i]-min]-1] = unsorted[i];
		--c[unsorted[i]-min];
	}
}

void test_counting_sort_internal(int arr_a[], int n) {
	std::vector<int> unsorted(arr_a, arr_a + n);
	std::vector<int> sorted;
	counting_sort(unsorted, sorted);
	std::copy(unsorted.begin(), unsorted.end(), std::ostream_iterator<int>(std::cout, " ") ); 
	std::cout << std::endl;
	std::copy(sorted.begin(),sorted.end(),std::ostream_iterator<int>(std::cout, " ") );
	std::cout << std::endl;
}

void test_counting_sort(){
	int arr_a[] = {2, 5, 3, 0, 2, 3, 0, 3};
	test_counting_sort_internal(arr_a, sizeof(arr_a)/sizeof(int) );

	int arr_b[] = {6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2};
	test_counting_sort_internal(arr_b, sizeof(arr_b)/sizeof(int) );
}